% !TEX program = xelatex
\documentclass{article}
\usepackage{xeCJK}
\usepackage{amsmath}
\usepackage{booktabs}
\usepackage{pifont}
\title{离散数学作业(习题一T12(1,2),13,14)}
\author{2020141460280张家帅}

\begin{document}
\maketitle
\section{习题一}
\subsection{T12}
\subsubsection{(1)}
$P\rightarrow((Q\wedge R)\rightarrow S)$

真值表法：
\begin{tabular}{cccc|c}
	\toprule
	P & Q & R & S & 原式 \\
	\midrule
	0 & 0 & 0 & 0 & 1    \\
	0 & 0 & 0 & 1 & 1    \\
	0 & 0 & 1 & 0 & 1    \\
	0 & 0 & 1 & 1 & 1    \\
	0 & 1 & 0 & 0 & 1    \\
	0 & 1 & 0 & 1 & 1    \\
	0 & 1 & 1 & 0 & 1    \\
	0 & 1 & 1 & 1 & 1    \\
	1 & 0 & 0 & 0 & 1    \\
	1 & 0 & 0 & 1 & 1    \\
	1 & 0 & 1 & 0 & 1    \\
	1 & 0 & 1 & 1 & 1    \\
	1 & 1 & 0 & 0 & 1    \\
	1 & 1 & 0 & 1 & 1    \\
	1 & 1 & 1 & 0 & 0    \\
	1 & 1 & 1 & 1 & 1    \\
	\bottomrule
\end{tabular} \\

主合取范式：\\

$\neg P\vee\neg Q\vee\neg R\vee S$ \\

等价变换法：\\

\begin{align}
	                  & P\rightarrow((Q\wedge R)\rightarrow S)\notag                                                                                                                                       \\
	\Leftrightarrow{} & \neg P\vee((Q\wedge R)\rightarrow S)\notag                                                                                                                                         \\
	\Leftrightarrow{} & \neg P\vee(\neg(Q\wedge R)\vee S)\notag                                                                                                                                            \\
	\Leftrightarrow{} & \neg P\vee\neg(Q\wedge R)\vee S\notag                                                                                                                                              \\
	\Leftrightarrow{} & (\neg P\wedge\neg Q\wedge\neg R\wedge\neg S)\vee(\neg P\wedge\neg Q\wedge\neg R\wedge S)\vee(\neg P\wedge\neg Q\wedge R\wedge\neg S)\vee(\neg P\wedge\neg Q\wedge R\wedge S)\notag \\
	                  & \vee(\neg P\wedge Q\wedge\neg R\wedge\neg S)\vee(\neg P\wedge Q\wedge\neg R\wedge S)\vee(\neg P\wedge Q\wedge R\wedge\neg S)\vee(\neg P\wedge Q\wedge R\wedge S)\notag             \\
	                  & ( P\wedge\neg Q\wedge\neg R\wedge\neg S)\vee( P\wedge\neg Q\wedge\neg R\wedge S)\vee( P\wedge\neg Q\wedge R\wedge\neg S)\vee( P\wedge\neg Q\wedge R\wedge S)\notag                 \\
	                  & \vee( P\wedge Q\wedge\neg R\wedge\neg S)\vee( P\wedge Q\wedge\neg R\wedge S)\vee( P\wedge Q\wedge R\wedge S)\notag
\end{align}
主析取范式：
\begin{align}
	 & (\neg P\wedge\neg Q\wedge\neg R\wedge\neg S)\vee(\neg P\wedge\neg Q\wedge\neg R\wedge S)\vee(\neg P\wedge\neg Q\wedge R\wedge\neg S)\vee(\neg P\wedge\neg Q\wedge R\wedge S)\notag \\
	 & \vee(\neg P\wedge Q\wedge\neg R\wedge\neg S)\vee(\neg P\wedge Q\wedge\neg R\wedge S)\vee(\neg P\wedge Q\wedge R\wedge\neg S)\vee(\neg P\wedge Q\wedge R\wedge S)\notag             \\
	 & ( P\wedge\neg Q\wedge\neg R\wedge\neg S)\vee( P\wedge\neg Q\wedge\neg R\wedge S)\vee( P\wedge\neg Q\wedge R\wedge\neg S)\vee( P\wedge\neg Q\wedge R\wedge S)\notag                 \\
	 & \vee( P\wedge Q\wedge\neg R\wedge\neg S)\vee( P\wedge Q\wedge\neg R\wedge S)\vee( P\wedge Q\wedge R\wedge S)\notag
\end{align}

\subsubsection{(2)}
$(\neg P\vee\neg Q)\rightarrow(P\leftrightarrow\neg Q)$\\

真值表法：\\

\begin{tabular}{cc|c}
	\toprule
	P & Q & 原式 \\
	\midrule
	0 & 0 & 0    \\
	0 & 1 & 1    \\
	1 & 0 & 1    \\
	1 & 1 & 1    \\
	\bottomrule
\end{tabular} \\

主合取范式： \\

$P\vee Q$ \\

等价变换法：\\

\begin{align}
	                  & (\neg P\vee\neg Q)\rightarrow(P\leftrightarrow \neg Q)\notag                      \\
	\Leftrightarrow{} & \neg(\neg P\vee\neg Q)\vee((P\rightarrow\neg Q)\wedge(\neg Q\rightarrow P))\notag \\
	\Leftrightarrow{} & (P\wedge Q)\vee((\neg P\vee\neg Q)\wedge(Q\vee P))\notag                          \\
	\Leftrightarrow{} & (P\wedge Q)\vee(\neg P\wedge Q)\vee(P\wedge\neg Q)\notag
\end{align}

主析取范式：\\

$(P\wedge Q)\vee(\neg P\wedge Q)\vee(P\wedge\neg Q)$
\subsection{T13}
\subsubsection{(1)}

\begin{align}
	                  & (P\rightarrow Q)\rightarrow(P\wedge Q)\notag \\
	\Leftrightarrow{} & \neg(\neg P\vee Q)\vee(P\wedge Q)\notag      \\
	\Leftrightarrow{} & (P\wedge\neg Q)\vee(P\wedge Q)
\end{align} \\

\begin{align}
	                  & (\neg P\rightarrow Q)\wedge(Q\rightarrow P)\notag \\
	\Leftrightarrow{} & (P\vee Q)\wedge(P\vee\neg Q)\notag                \\
	\Leftrightarrow{} & (P\wedge\neg Q)\vee(P\wedge Q)
\end{align}

(1)式、(2)式的主析取范式相同，所以等价

\subsection{T14}

画出真值表，排除掉不符合规则的情况后，得到三种情况如下：\\

\begin{tabular}{cccc|c}
	\toprule
	A & B & C & D & 是否符合情况 \\
	\midrule
	0 & 1 & 0 & 1 & 1            \\
	1 & 0 & 0 & 1 & 1            \\
	1 & 0 & 1 & 0 & 1            \\
	\bottomrule
\end{tabular}\\

所以最终结果为B和D去或者A和D去或者A和C去

\subsection{T15}
\subsubsection{(1)}
要证$ P\rightarrow Q\Rightarrow P\rightarrow(P\wedge Q) $，即证$ (P\rightarrow Q)\rightarrow(P\rightarrow(P\wedge Q)) $为永真式
\begin{align}
	                  & (P\rightarrow Q)\rightarrow(P\rightarrow(P\wedge Q))\notag \\
	\Leftrightarrow{} & (\neg P\vee Q)\rightarrow(\neg P\vee(P\wedge Q))\notag     \\
	\Leftrightarrow{} & \neg(\neg P\vee Q)\vee(\neg P\vee(P\wedge Q))\notag        \\
	\Leftrightarrow{} & (P\wedge\neg Q)\vee\neg P\vee(P\wedge Q)\notag             \\
	\Leftrightarrow{} & P\vee\neg P\notag                                          \\
	\Leftrightarrow{} & T\notag
\end{align} \\

所以$ P\rightarrow Q\Rightarrow P\rightarrow(P\wedge Q) $成立
\subsubsection{(3)}
要证$ P\wedge\neg P\wedge R\Rightarrow S $，即证$ (P\wedge\neg P\wedge R)\rightarrow S $为永真式
\begin{align}
	                  & (P\wedge\neg P\vee R)\rightarrow S\notag \\
	\Leftrightarrow{} & (F\wedge R)\rightarrow S\notag           \\
	\Leftrightarrow{} & F\rightarrow S\notag                     \\
	\Leftrightarrow{} & T\vee S\notag                            \\
	\Leftrightarrow{} & T\notag
\end{align} \\

所以$ P\wedge\neg P\wedge R\Rightarrow S $成立
\subsection{T19}
\subsection{(2)}
$ (P\rightarrow(Q\vee\neg R))\wedge(Q\rightarrow(P\wedge R))\Rightarrow P\rightarrow R $ \\

\begin{align}
	                  & ((P\rightarrow(Q\vee\neg R))\wedge(Q\rightarrow(P\wedge R))\rightarrow(P\rightarrow R))\notag   \\
	\Leftrightarrow{} & ((\neg P\vee(Q\vee\neg R))\wedge(\neg Q\vee(P\wedge R))\rightarrow(\neg P\vee R))\notag         \\
	\Leftrightarrow{} & \neg((\neg P\vee Q\vee\neg R)\wedge(\neg Q\vee P\wedge R))\vee\neg P\vee R\notag                \\
	\Leftrightarrow{} & (P\wedge\neg Q\wedge R)\vee(\neg P\wedge\neg Q)\vee(\neg Q\wedge\neg R)\vee\neg P\wedge R\notag \\
	\Leftrightarrow{} & \neg P\vee R\vee(\neg Q\wedge\neg R)\notag
\end{align}

不是永真式，所以蕴涵关系式$ (P\rightarrow(Q\vee\neg R))\wedge(Q\rightarrow(P\wedge R))\Rightarrow P\rightarrow R $不成立
\subsubsection{(4)}
$ (P\vee Q)\wedge(P\rightarrow\neg Q)\wedge(P\rightarrow R)\Rightarrow R $ \\

\begin{align}
	                  & ((P\vee Q)\wedge(P\rightarrow\neg Q)\wedge(P\rightarrow R))\rightarrow R\notag \\
	\Leftrightarrow{} & \neg((P\vee Q)\wedge(\neg P\vee\neg Q)\wedge(\neg P\vee R))\vee R\notag        \\
	\Leftrightarrow{} & (\neg P\wedge\neg Q)\vee(P\wedge Q)\vee(P\wedge\neg R)\vee R\notag
\end{align}

不是永真式，所以蕴涵关系式$ (P\vee Q)\wedge(P\rightarrow\neg Q)\wedge(P\rightarrow R)\Rightarrow R $不成立
\subsection{T20}
\subsubsection{(2)}
证明$ P\rightarrow B $是前提$ {(P\vee Q)\rightarrow(R\wedge S), (S\vee E)\rightarrow B} $的有效结论 \\

\begin{tabular}{c|c|c}
	\toprule
	步骤 & 公式                                     & 使用规则    \\
	\midrule
	1    & $ P $                                    & P(附加前提) \\
	2    & $ P\vee Q $                              & T1I         \\
	3    & $ (P\vee Q)\rightarrow(R\rightarrow S) $ & P           \\
	4    & $ R\wedge S $                            & T2,3I       \\
	5    & $ S $                                    & T4I         \\
	6    & $ S\vee E $                              & T5I         \\
	7    & $ (S\vee E)\rightarrow B $               & P           \\
	8    & $ B $                                    & T6,7I       \\
	9    & $ P\rightarrow B $                       & CP1,8       \\
	\bottomrule
\end{tabular}
\subsection{(4)}
证明$ \neg P $是前提$ {(R\rightarrow Q)\wedge(R\rightarrow S),(Q\rightarrow E)\wedge(S\rightarrow B),\neg(E\wedge B),P\rightarrow R} $的有效结论 \\

\begin{tabular}{c|c|c}
	\toprule
	步骤 & 公式                                       & 使用规则 \\
	\midrule
	1    & $ (Q\rightarrow E)\wedge(S\rightarrow B) $ & P        \\
	2    & $ \neg(E\wedge B)\wedge\neg(Q\wedge S) $   & T1E      \\
	3    & $ \neg(E\wedge B) $                        & P        \\
	4    & $ \neg(Q\wedge S) $                        & T2,3I    \\
	5    & $ (R\rightarrow Q)\wedge(R\rightarrow S) $ & P        \\
	6    & $ \neg(Q\wedge S)\rightarrow\neg R $       & T5E      \\
	7    & $ P\rightarrow R $                         & P        \\
	8    & $ \neg R\rightarrow\neg P $                & T7E      \\
	9    & $ \neg P $                                 & T6,8I    \\
	\bottomrule
\end{tabular}
\subsection{T21}
\subsubsection{(2)}
设\\
P:被盗现场留下了痕迹\\
Q:失窃时，小花正在卡拉OK厅\\
R:失窃时，小英正在卡拉OK厅\\
S:失窃时小胖就在附近\\
A:小胖偷了东西\\
B:金刚偷了东西\\
C:瘦子偷了东西\\

则$ \neg P,Q\vee R,S\rightarrow(P\wedge A),Q\rightarrow B,\neg S\rightarrow \neg R,R\rightarrow C $ \\

\begin{tabular}{c|c|c}
	\toprule
	步骤 & 公式                                    & 使用规则 \\
	\midrule
	1    & $ S\rightarrow(P\wedge A) $             & P        \\
	2    & $ (\neg P\vee\neg A)\rightarrow\neg S $ & T1E      \\
	3    & $ \neg P $                              & P        \\
	4    & $ \neg P\vee\neg A $                    & T3I      \\
	5    & $ \neg S $                              & T2,4I    \\
	6    & $ \neg S\rightarrow\neg R $             & P        \\
	7    & $ \neg R $                              & T5,6I    \\
	8    & $ Q\vee R $                             & P        \\
	9    & $ Q $                                   & T7,8I    \\
	10   & $ Q\rightarrow B $                      & P        \\
	11   & $ B $                                   & T9,10I   \\
	\bottomrule
\end{tabular}\\

所以金刚是最可能的犯罪嫌疑人
\subsection{T23}
\subsubsection{(1)}
\begin{align}
	                  & (R\rightarrow\neg Q)\wedge(R\vee S)\wedge(S\rightarrow\neg Q)\wedge(P\rightarrow Q)\wedge P\notag \\
	\Leftrightarrow{} & (\neg R\vee\neg Q)\wedge(R\vee S)\wedge(\neg S\vee\neg Q)\wedge(\neg P\vee Q)\wedge P\notag
\end{align}

得到子句集$ \{\neg R\vee\neg Q,R\vee S,\neg S\vee \neg Q,\neg P\vee Q,P\} $\\

\begin{tabular}{c|c|c}
	\toprule
	步骤 & 公式                 & 使用规则    \\
	\midrule
	1    & $ \neg R\vee\neg Q $ & P(引用子句) \\
	2    & $ R\vee S $          & P(引用子句) \\
	3    & $ \neg S\vee\neg Q $ & P(引用子句) \\
	4    & $ \neg P\vee Q $     & P(引用子句) \\
	5    & $ P $                & P(引用子句) \\
	6    & $ S\vee\neg Q $      & 由1,2归结   \\
	7    & $ \neg Q $           & 由3,6归结   \\
	8    & $ \neg P $           & 由4,7归结   \\
	9    & $ F $                & 导出空子句  \\
	\bottomrule
\end{tabular}
\subsubsection{(3)}
\begin{align}
	                  & (P\rightarrow(Q\rightarrow R))\wedge(Q\rightarrow(R\rightarrow S))\wedge\neg(P\rightarrow(Q\rightarrow S))\notag \\
	\Leftrightarrow{} & (\neg P\vee(\neg Q\vee R))\wedge(\neg Q\vee(\neg R\vee S))\wedge\neg(\neg P\vee\neg Q\vee S)\notag               \\
	\Leftrightarrow{} & (\neg P\vee\neg Q\vee R)\wedge(\neg Q\vee\neg R\vee S)\wedge P\wedge Q\wedge\neg S\notag
\end{align}

得到子句集$ \{(\neg P\vee\neg Q\vee R),(\neg Q\vee\neg R\vee S), P, Q,\neg S\} $\\

\begin{tabular}{c|c|c}
	\toprule
	步骤 & 公式                       & 使用规则    \\
	\midrule
	1    & $ \neg P\vee\neg Q\vee R $ & P(引用子句) \\
	2    & $ \neg Q\vee\neg R\vee S $ & P(引用子句) \\
	3    & $ P $                      & P(引用子句) \\
	4    & $ Q $                      & P(引用子句) \\
	5    & $ \neg S $                 & P(引用子句) \\
	6    & $ \neg P\vee\neg Q\vee S $ & 由1,2归结   \\
	7    & $ \neg Q\vee S $           & 由3,6归结   \\
	8    & $ S $                      & 由5,7归结   \\
	9    & $ F $                      & 导出空子句  \\
	\bottomrule
\end{tabular}
\end{document}
